#include <stdio.h>
#include <stdlib.h>

typedef struct no{
	int info;
	struct no *proximo;
	struct no *anterior;
}no;


void quickSortLL(no *lista, no *inicio, no *fim){
	no *no_passeio;
	no *pivo;
	no *CopInicio=inicio,*CopFim=fim,*CopPivo;

	if(inicio==fim)
		return;

	no_passeio=inicio;
	pivo=inicio;

	while(no_passeio!=fim->proximo && no_passeio!=NULL && no_passeio->proximo!=NULL){
		if(no_passeio->info<pivo->info){
			no *temporario=no_passeio;
			no_passeio=no_passeio->proximo;

			temporario->anterior->proximo=temporario->proximo;
			temporario->proximo->anterior=temporario->anterior;

			temporario->proximo=CopInicio;
			temporario->anterior=CopInicio->anterior;
			CopInicio->anterior=temporario;
			temporario->anterior->proximo=temporario;
			
			if(temporario==CopFim)
				CopFim=CopFim->anterior;

			CopInicio=temporario;
			
		}
		else
		no_passeio=no_passeio->proximo;
	}

	CopPivo=pivo;
	if(CopInicio!=NULL && CopPivo!=NULL)
		quickSortLL(lista,CopInicio,CopPivo);
	if(CopPivo!=NULL && CopFim!=NULL)
		quickSortLL(lista,CopPivo->proximo,CopFim);
}


void insere_no_inicio_duplo(struct no *primeiro, int valor){
	struct no *novo;
	novo=(struct no*) malloc(sizeof(struct no));
	
	novo->proximo=primeiro->proximo;
	primeiro->proximo=novo;
	novo->info=valor;
	novo->anterior=primeiro;

	if(novo->proximo!=NULL)
		novo->proximo->anterior=novo;

}

void percorreLD_IF(struct no *primeiro){
	struct no *percorre;

	percorre=primeiro;

	while(percorre->proximo!=NULL){
		if(percorre!=primeiro)
			printf("\n%i\n",percorre->info);
		percorre=percorre->proximo;
	}
	if(percorre!=primeiro)
		printf("\n%i\n\n",percorre->info);

}


void main (){
	no *cabeca=(no*) malloc(sizeof(no));
	no *sentinela=(no*) malloc(sizeof(no));
	int i;

	cabeca->proximo=sentinela;
	sentinela->anterior=cabeca;
	cabeca->anterior=NULL;
	sentinela->proximo=NULL;
	cabeca->info=9999;
	sentinela->info=8888;

	for(i=0;i<2000;i++)
		insere_no_inicio_duplo(cabeca,rand()%100);

	percorreLD_IF(cabeca);

	quickSortLL(cabeca,cabeca->proximo,sentinela->anterior);

	percorreLD_IF(cabeca);

	system("PAUSE");
	return;


}
